home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 February: Tool Chest / Dev.CD Feb 94.toast / Tool Chest / Networking & Communications / Network Watch (DMZ) 1.0 / qsort.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-17  |  2.0 KB  |  132 lines  |  [TEXT/KAHL]
  1.  
  2. /*
  3.  *  qsort.c
  4.  *
  5.  *  Copyright (c) 1989 Symantec Corporation.  All rights reserved.
  6.  *
  7.  */
  8.  
  9. #include "stdlib.h"
  10.  
  11. static char *qBase;
  12. static size_t qSize;
  13. static int (*qCompare)();
  14.  
  15. static int std_compare(size_t, size_t);
  16. static void std_swap(size_t, size_t);
  17.  
  18. static void qsort1(size_t, size_t);
  19. static int (*q1Compare)();
  20. static void (*q1Swap)();
  21.  
  22.  
  23. /* ---------- standard quicksort ---------- */
  24.  
  25.  
  26. void qsort(base, n, size, compare)
  27. void *base;
  28. size_t n, size;
  29. int (*compare)();
  30. {
  31.     qBase = base;
  32.     /* qSize = (size + 1) & ~1;  why is this - pvh 8/12/89 ???? */
  33.     qSize = size; /* changed to use without complement  - pvh 8/12/89 */
  34.     qCompare = compare;
  35.     _qsort(n, std_compare, std_swap);
  36. }
  37.  
  38.  
  39. static int
  40. std_compare(i, j)
  41. size_t i, j;
  42. {
  43.     return((*qCompare)(qBase + i * qSize, qBase + j * qSize));
  44. }
  45.  
  46.  
  47. static void
  48. std_swap(i, j)
  49. size_t i, j;
  50. {
  51.     register void *p = qBase + i * qSize;
  52.     register void *q = qBase + j * qSize;
  53.     
  54.     asm {
  55.         move.l    qSize,d0
  56. @1        move.b    (p)+,d1
  57.         eor.b    d1,(q)+
  58.         subq.l    #1,d0
  59.         bne.s    @1
  60.     }
  61.     asm {
  62.         move.l    qSize,d0
  63. @2        move.b    -(q),d1
  64.         eor.b    d1,-(p)
  65.         subq.l    #1,d0
  66.         bne.s    @2
  67.     }
  68.     asm {
  69.         move.l    qSize,d0
  70. @3        move.b    (p)+,d1
  71.         eor.b    d1,(q)+
  72.         subq.l    #1,d0
  73.         bne.s    @3
  74.     }
  75. }
  76.  
  77.  
  78. /* ---------- general quicksort ---------- */
  79.  
  80.  
  81. void
  82. _qsort(n, compare, swap)
  83. size_t n;
  84. int (*compare)();
  85. void (*swap)();
  86. {
  87.     q1Compare = compare;
  88.     q1Swap = swap;
  89.     qsort1(0, n);
  90. }
  91.  
  92.  
  93. /*
  94.  *  sort elements "first" through "last"-1
  95.  *
  96.  */
  97.  
  98. static void
  99. qsort1(first, last)
  100. size_t first, last;
  101. {
  102.     static size_t i;        /*  "static" to save stack space  */
  103.     size_t j;
  104.  
  105.     while (last - first > 1) {
  106.         i = first;
  107.         j = last;
  108.         for (;;) {
  109.             while (++i < last && (*q1Compare)(i, first) < 0)
  110.                 ;
  111.             while (--j > first && (*q1Compare)(j, first) > 0)
  112.                 ;
  113.             if (i >= j)
  114.                  break;
  115.             (*q1Swap)(i, j);
  116.         }
  117.         if (j == first) {
  118.             ++first;
  119.             continue;
  120.         }
  121.         (*q1Swap)(first, j);
  122.         if (j - first < last - (j + 1)) {
  123.             qsort1(first, j);
  124.             first = j + 1;    /*  qsort1(j + 1, last);  */
  125.         }
  126.         else {
  127.             qsort1(j + 1, last);
  128.             last = j;        /*  qsort1(first, j);  */
  129.         }
  130.     }
  131. }
  132.